package com.lw.leetcode.greedy;

import java.util.Stack;

/**
 * 402. 移掉K位数字
 *
 * @Author liw
 * @Date 2021/5/13 10:55
 * @Version 1.0
 */
public class RemoveKdigits {

    public static void main(String[] args) {
        RemoveKdigits test = new RemoveKdigits();
        String s = test.removeKdigits("12", 1);
        System.out.println(s);
    }

    public String removeKdigits(String num, int k) {
        int length = num.length();
        int l = length - k;
        if (l == 0) {
            return "0";
        }
        Stack<Character> stack = new Stack<>();
        char[] arr = new char[l];
        stack.add(num.charAt(0));
        int i = 1;
        int size = 0;
        a:
        for (; i < length; i++) {
            char c = num.charAt(i);
            while (!stack.isEmpty()) {
                if (stack.peek() > c) {
                    stack.pop();
                    size = stack.size();
                    if (size + length - i == l) {
                        break a;
                    }
                } else {
                    break;
                }
            }
            stack.add(c);
            size = stack.size();
        }

        int end = Math.min(size, l);
        for (int j = end - 1; j >= 0; j--) {
            arr[j] = stack.pop();
        }

        for (int j = end; j < l; j++) {
            arr[j] = num.charAt(++i);
        }
        i = 0;
        for (; i < l; i++) {
            if (arr[i] != '0') {
                break;
            }
        }
        if (i == l) {
            return "0";
        }
        return new String(arr, i, l - i);
    }

}
